#ifndef LEETCODE_CN_CPP_PROBLEMS_115_H
#define LEETCODE_CN_CPP_PROBLEMS_115_H

#include <string>
#include <vector>

using namespace std;

namespace problem_115
{

class Solution
{
public:
    int numDistinct(string s, string t)
    {
        if (s.size() < t.size())
            return 0;
        if (t.empty())
            return 1;
        // dp[i][j]表示s的前i个字符和t的前j个字符的子序列的个数
        // dp[i][j] = dp[i - 1][j] 当s[i - 1] != t[j - 1]，也就是s新增的字符和t不的末尾字符不匹配
        // dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] 当s[i - 1] == t[j - 1]，
        // 也就是s新增的字符与t末尾字符匹配，可以看作是要s[i - 1]或者不要它，
        //如果要s[i - 1]则为dp[i - 1][j - 1]，如果不要则是dp[i - 1][j]
        int rows = s.size() + 1, cols = t.size() + 1;
        vector<vector<long long>> dp(rows, vector<long long>(cols, 0));
        for (int j = 1; j < cols; ++j)
        {
            for (int i = j; i < rows; ++i)
            {
                if (j == 1)
                {
                    dp[i][j] = dp[i - 1][j] + (s[i - 1] == t[j - 1] ? 1 : 0);
                    continue;
                }
                if (i == j)
                {
                    if (dp[i - 1][j - 1] == 1 && s[i - 1] == t[j - 1])
                        dp[i][j] = 1;
                    else
                        dp[i][j] = 0;
                    continue;
                }
                if (s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};

}; // namespace problem_115

#endif //LEETCODE_CN_CPP_PROBLEMS_115_H
